#include <string.h>

#include <kernel.h>

#define MEM_MAGIC      0x1ea01ea0                // 幻数
#define MEM_FREE       (MEM_MAGIC | 0x00)    // 未使用状态
#define MEM_USE        (MEM_MAGIC | 0x01)    // 使用状态
#define MIN_MEM_SIZE   12  // 最小可分配的内存大小

/* 字节对齐后的内存管理结构大小 */
#define HEAP_MEM_ITEM_SIZE       __align(sizeof(struct heap_mem_item), 4)

/* 判断内存是否为使用状态 */
#define mem_is_use(item)  ((item)->magic & 0x1)

#define get_mem_prev_item(item)  list_entry(item->list.prev, struct heap_mem_item, list)
#define get_mem_next_item(item)  list_entry(item->list.next, struct heap_mem_item, list)

struct heap_mem_item {
	uint32_t magic;        /* 幻数 */
	struct list list; /* list结构 */
};

struct heap_mem {
	unsigned long mem_size;          /* 可分配内存总大小 */
	struct heap_mem_item *lfree;         /* 第一块空闲内存 */
	struct list *heap_head;    /* 整个分配内存链表头 */
	struct heap_mem_item *heap_end; /* 堆的末尾 */
};

static struct heap_mem heap_mem;

/* 合并空闲内存 */
static void merge_free_mem(struct heap_mem_item *item)
{
	struct heap_mem_item *tmp;
	/* 判断该内存块前一个内存是否是空闲内存，如果是空闲内存就将两块内存合并 */
	if (!mem_is_use(get_mem_prev_item(item))) {
		/* 保存上一个内存管理块地址 */
		tmp = get_mem_prev_item(item);
		/* 这块内存已经被非法修改了，无法完成合并 */
		if ((tmp->magic & 0xFFFF0000) != (MEM_MAGIC & 0xFFFF0000))
			return;
		/* 删除当前节点 */
		list_del(&item->list);
		/* 当前内存块地址变动为上一个内存块的地址 */
		item = tmp;
		/* 更新lfree指针 */
		heap_mem.lfree = item;
	}

	/* 判断该内存块下一个内存是否是空闲内存，如果是空闲内存就将两个内存合并 */
	if (!mem_is_use(get_mem_next_item(item))) {
		/* 这块内存已经被非法修改了，无法完成合并 */
		if ((get_mem_next_item(item)->magic & 0xFFFF0000) != (MEM_MAGIC & 0xFFFF0000))
			return;
		/* 将下一个内存块删除，相当于合并了下一个内存块 */
		list_del(item->list.next);
	}
}

/* 计算当前item的剩余空间大小 */
static inline unsigned long calc_free_mem_size(struct heap_mem_item *item)
{
	/* 下一个节点的起始地址 */
	unsigned long next_addr = (unsigned long)list_entry(item->list.next, struct heap_mem_item, list);
	/* 当前节点的起始地址 */
	unsigned long current_addr = (unsigned long)item;
	/* 返回去掉管理数据大小的空闲内存大小 */
	return (next_addr - current_addr) - HEAP_MEM_ITEM_SIZE;
}

/* 内存管理初始化函数 */
void mem_init(void *begin_addr, void *end_addr)
{
	struct heap_mem_item *mem_item;

	/* 向上4字节对齐 */
	unsigned long begin_align = __align((unsigned long)begin_addr, 4);
	/* 向下四字节对齐 */
	unsigned long end_align = __align_down((unsigned long)end_addr, 4);

	/* 计算字节对齐后的可分配内存大小 */
	heap_mem.mem_size = end_align - begin_align - 2 * HEAP_MEM_ITEM_SIZE;

	/* 将可分配内存的末尾保存下来 */
	heap_mem.heap_end = (struct heap_mem_item *)(begin_align + heap_mem.mem_size + HEAP_MEM_ITEM_SIZE);
	/* 将内存末尾标记为已使用 */
	heap_mem.heap_end->magic = MEM_USE;

	/* 第一个节点为可分配内存的开始位置 */
	mem_item = (struct heap_mem_item *)begin_align;
	/* 将内存默认初始化为未使用状态 */
	mem_item->magic = MEM_FREE;
	/* 设置内存管理链表头 */
	heap_mem.heap_head = &mem_item->list;
	/* 第一个节点初始化 */
	init_list(&mem_item->list);
	/* 设置第一个空闲块位置 */
	heap_mem.lfree = mem_item;

	/* 初始化堆尾 */
	init_list(&heap_mem.heap_end->list);
	/* 将堆尾加入到链表中 */
	list_add_tail(&heap_mem.heap_end->list, heap_mem.heap_head);
}

/* 内存分配函数 */
void *mem_alloc(size_t size)
{
	struct heap_mem_item *item, *tmp_item;
	long free_mem_size = 0;

	/* 不能分配0字节的空间 */
	if (size == 0)
		return NULL;

	/* 对分配的内存大小，按照四字节对齐 */
	size = __align(size, 4);

	/* 判断是否超过内存总大小 */
	if (size > heap_mem.mem_size)
		return NULL;

	/* 如果字节对齐后的大小，小于最小分配内存的大小，那就将需要分配的内存大小设置为最小的内存分配大小 */
	if (size < MIN_MEM_SIZE)
		size = MIN_MEM_SIZE;

	/* 从第一块空闲内存开始，遍历整个链表 */
	list_for_each_entry(item, heap_mem.lfree->list.prev, list) {
		/* 如果当前内存不是空闲内存则跳过当前循环 */
		if (mem_is_use(item))
			continue;

		/* 计算当前的空闲内存大小 */
		free_mem_size = calc_free_mem_size(item);

		/* 当前空闲内存小于需要分配的内存则跳过当前循环 */
		if (free_mem_size < size)
			continue;

		/* *
		 * 判断是否需要分割内存，如果去掉当前分配的内存大小后还可以满足可分配的最小内存大小，那就将
		 * 这块内存分割，如果不满足，那就将这一整块的内存返回
		 */
		if ((base_t)(free_mem_size - size - HEAP_MEM_ITEM_SIZE) >= MIN_MEM_SIZE) {
			/* 建立一个新的内存管理节点 */
			tmp_item = (struct heap_mem_item *)((unsigned long)item + size + HEAP_MEM_ITEM_SIZE);
			/* 新的内存管理节点标记为未使用 */
			tmp_item->magic = MEM_FREE;
			/* 将新的内存管理节点加入到链表中 */
			list_add(&tmp_item->list, &item->list);
			/* 更新lfree指针 */
			heap_mem.lfree = tmp_item;
		} else {
			/* 找到下一个内存未使用的节点 */
			list_for_each_entry(tmp_item, &item->list, list) {
				/* 如果当前内存不是空闲内存则跳过当前循环 */
				if (!mem_is_use(tmp_item)) {
					/* 更新lfree指针 */
					heap_mem.lfree = tmp_item;

					/* 更新后跳出循环 */
					break;
				}
			}
		}

		item->magic = MEM_USE;

		/* 返回分配的内存起始地址 */
		return (void *)((unsigned long)item + HEAP_MEM_ITEM_SIZE);
	}

	/* 没有找到合适的内存分配，返回空，内存分配失败 */
	return NULL;
}

/* 释放分配的内存 */
void mem_free(void *ptr)
{
	struct heap_mem_item *item;

	/* 给定的内存并不是通过mem_alloc分配的，无法释放 */
	if ((unsigned long)ptr < (unsigned long)heap_mem.heap_head)
		return;

	/* 拿到这块内存的管理头 */
	item = (struct heap_mem_item *)((uint8_t *)ptr - HEAP_MEM_ITEM_SIZE);

	/* 这块内存已经被非法修改了无法释放 */
	if ((item->magic & 0xFFFF0000) != (MEM_MAGIC & 0xFFFF0000))
		return;

	/* 将当前的内存块标为未使用 */
	item->magic = MEM_FREE;

	/* 更新lfree指针 */
	heap_mem.lfree = item;

	/* 合并相邻的空闲内存 */
	merge_free_mem(item);
}

/* 重新分配内存 */
void *mem_realloc(void *ptr, size_t size)
{
	struct heap_mem_item *item;
	size_t free_mem_size;
	void *tmp;

	/* 给定的内存并不是通过mem_alloc分配的 */
	if ((unsigned long)ptr < (unsigned long)heap_mem.heap_head)
		return NULL;

	/* 拿到这块内存的管理头 */
	item = (struct heap_mem_item *)((uint8_t *)ptr - HEAP_MEM_ITEM_SIZE);

	/* 这块内存已经被非法修改了 */
	if ((item->magic & 0xFFFF0000) != (MEM_MAGIC & 0xFFFF0000))
		return NULL;

	/* 计算剩余空间大小 */
	free_mem_size = calc_free_mem_size(item);
	/* 如果当前节点剩余空间，满足分配需求则直接返回 */
	if (free_mem_size >= size)
		return ptr;

	/* 重新分配size大小的空间 */
	tmp = mem_alloc(size);
	/* tmp = NULL说明分配空间失败了，直接退出 */
	if (tmp == NULL)
		return NULL;
	/* 将原来的数据，拷贝到新分配的空间中 */
	memcpy(tmp, ptr, free_mem_size);
	/* 释放掉原来的内存 */
	mem_free(ptr);
	/* 返回分配内存的首地址 */
	return tmp;
}
